package lc;
import java.util.*;
import org.junit.*;
public class Ex139 {
    class Solution {
        public boolean wordBreak(String s, List<String> wordDict) {
            Map<Character, List<String>> dict = new HashMap<>();
            for (String str: wordDict) {
                char c = str.charAt(0);
                if (dict.containsKey(c)) {
                    dict.get(c).add(str);
                } else {
                    dict.put(c, new ArrayList<>(Arrays.asList(str)));
                }
            }
            return dfs(0, s.toCharArray(), dict);
        }
    
        public boolean dfs(int idx, char[] cs, Map<Character, List<String>> dict) {
            if (idx == cs.length) {
                return true;
            }
            List<String> cur = dict.get(cs[idx]);
            if (cur != null)  {
                loop: for (String s: cur) {
                    char[] ts = s.toCharArray();
                    int len = ts.length;
                    for (int j = 0; j < len; j++) {
                        if (j == cs.length || cs[j + idx] != ts[j]) {
                            continue loop;
                        }
                    }
                    boolean res = dfs(idx + len, cs, dict);
                    if (res) return true;
                }
            }
            return false;
        }
    }
    
    @Test
    public void test() {
        Solution s = new Solution();
        String[] strs = {"leet","code"};
        System.out.println(s.wordBreak("leetcode", Arrays.asList(strs)));
    }


    class Solution2 {
        public boolean wordBreak(String s, List<String> wordDict) {
            int n = s.length();
            Set<String> set = new HashSet<>(wordDict);
            int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
            for (int i = 0; i < wordDict.size(); i++) {
                int size = wordDict.get(i).length();
                min = Math.min(min, size);
                max = Math.max(max, size);
            }
            boolean[] f = new boolean[n + 1];
            f[0] = true;
    
            for (int i = 1; i <= n; i++) {
                if (f[i - 1]) {
                    //前面n-1的字符串得到的才有意义
                    for (int j = i; j <= n; j++) {
                        if (j - i + 1 < min || f[j]) {
                            continue;
                        }
                        if (j - i + 1 > max) {
                            break;
                        }
                        String t = s.substring(i - 1, j);
                        if (set.contains(t)) {
                            f[j] = true;
                        }
                    }
                }
            }
            return f[n];
        }
    }

    @Test
    public void test2() {
        Solution2 s = new Solution2();
        String[] strs = {"a","abc","b","cd"};
        System.out.println(s.wordBreak("abcd", Arrays.asList(strs)));
    }
}
